package 二叉树题目.二叉树的层序遍历;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> arrayList = new ArrayList();
        if (root == null){
            return arrayList;
        }
        if (root.left == null && root.right == null){
            ArrayList tmpList = new ArrayList<>();
            tmpList.add(root.val);
            arrayList.add(tmpList);
            return arrayList;
        }
        // 建立个队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            int size = deque.size();
            ArrayList tmpList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                if (cur.left != null){
                    deque.offer(cur.left);
                }
                if (cur.right != null){
                    deque.offer(cur.right);
                }
                tmpList.add(cur.val);
            }
            arrayList.add(tmpList);
        }
        return arrayList;
    }
}
